A very large number of important processes and methods use an auxiliary input which is assumed to be truly random. Examples of such processes and methods include sorting, simulation and testing of complex systems, encryption, and many other cryptographic primitives. Producing a truly random auxiliary input of sufficient length is difficult. Typically, the auxiliary input is produced by a pseudo-random bit generator. Informally, a pseudo-random bit generator is any process or method which takes a short truly random string and produces a long "pseudo-random" string.
Many pseudo-random bit generators have been proposed and discussed in prior art literature, such as the popular linear congruential bit generator. In evaluating the utility of these bit generators, the conventional approach is to subject each bit generator to a standard regimen of empirical and analytical statistical tests to determine if the generators produce acceptable random bits. Those generators that pass the standard tests are often assumed to produce sufficiently good pseudo-random bit streams for the various purposes for which they are to be employed.
However, this assumption may be erroneous. For instance, it has been shown that the linear congruential bit generator is hardly general purpose since after observing its outputs for a short period, it becomes possible to compute the future outputs correctly. As another example, Monte Carlo simulations of a well-known physical system were recently shown to give results far from the known values when several well-known generators were used as input for the simulations.
While certain traditional generators may not be general purpose, they may be sufficient for certain purposes. For example, it has been shown that a few simple bit generators (including the linear congruential) are sufficient, in a rigorous sense, for a few specific applications. In short, there are examples where the traditional generators are known to be sufficient and there are examples where they are known to be insufficient. For all other cases there are no guarantees. Moreover, for complex methods and processes it is unlikely that the traditional generators will ever be proven to produce sufficiently random output.
Most recently, a different approach to pseudo-random bit generation has been developed based on the theory of "one-way" functions. For the immediate discussion, a one-way function is a function that is easy to compute but hard to invert on an overwhelming fraction of its range. With this notion in mind, a "cryptographically strong pseudo-random (CSPR) bit generator" is a generator that takes a short, truly random seed as input, then repeatedly uses a one-way function to produce a long pseudo-random string of bits such that there is no feasible technique or procedure which can distinguish between the outputs of a CSPR bit generator and a truly random string of bits. It is also known that a CSPR bit generator will pass all statistical tests whose running times are small compared to the time required to invert the one-way function. In particular, using CSPR bits rather than truly random bits in test or other application environments whose running times are small with respect to the time to invert a one-way function will not impact on the results in any demonstrable way.
In addition to the many direct applications of CSPR bit generators mentioned previously, these bit generators may be used to compute cryptographically strong pseudo-random functions (CSPR functions). These functions take two parameters, namely, a function index and a function input. For a randomly chosen fixed index, an adversary with no knowledge of the index cannot choose a function input and then predict even a single bit of the resulting function value in a feasible amount of time. This is true even if the adversary has already seen many function values for many function inputs of its choosing.
CSPR functions have several applications. Two important applications are as follows. First, they can be used in a simple protocol for identifying party A to party B over a non-secure channel when A and B share a secret key. The shared key is used as a CSPR function index. B queries any party on the channel claiming to be A with a random function input. Only A will be able to return the correct function value.
Second, CSPR functions can be used to distribute independent random bits to each of the processes in a parallel or distributed computation. A single seed is first broadcast to each process. This shared seed is used as the CSPR function index. Using its process identification number as a function input, each process computes a CSPR function value as its random seed. Each process may now use this seed and a CSPR bit generator to compute CSPR bits for its own use.
As indicated above, random number generators take a short random seed and produce a long sequence of pseudo-random numbers. In the Information Theoretic sense, correlation between the numbers generated by any such generator is inevitable and the issue of interest therefore is how this correlation affects their use. The shortcomings of prior art generators applied to the two important areas briefly discussed above, namely, Simulations (Randomized Algorithms), and Cryptography are further elucidated below.
Many simulations in engineering and scientific applications expect the generator to produce a sequence of uniformly distributed integers. Here the user is faced with a cyclic problem of estimating an unknown quantity to a great accuracy using simulations whose efficacy is unknown. Often the user does not have the "closed form" solution or alternative methods to verify the estimate obtained from simulations. To gain an indication of the quality of a generator, one may use standard randomness tests, but this is no guarantee that any new test will also be passed. Generators are usually characterized by their cycle lengths and possess some pair-wise independence properties in their outputs. Not much more can be proved in most cases. It would be valuable to have a fast generator with more provable properties.
The intuitive notions related to cryptographically strong generators have been formally well analyzed in the past decade starting with pioneering works of M. Blum, and S. Micali, titled "How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits," SIAM Journal on Computing, {13} (1984) 850-864 and A. C. Yao entitled "Theory and Applications of Trapdoor Functions," as published in the Proc. of IEEE Syrup. on Foundations of Computer Science (1982), pages 80-91. However, such generators are prohibitively slow in software. Besides, the constructions preserve security in a weak sense and only asymptotically (i.e. only for large enough seeds/keys) and the overhead in achieving a given security, say 2.sup.n, can be enormous and require keys of length n.sup.2 or cn, c&gt;&gt;1.
Often, high-speed cryptographic applications need a long string of random numbers, which can not be produced quickly enough directly from physical devices. Examples are One-Time Pad encryption, digital signatures, Bit-Commitment protocols, authentication schemes, or Zero-Knowledge protocols. The security of these applications can be compromised if the random strings are cryptographically weak. The art is devoid of teachings or suggestions for using relatively slow generators potentially within a preprocessing step to. generate a short but high quality random string of bits, and then producing many pseudo-random bits using only a few register operations (exclusive-OR and shift) per integer output. The slow generator may be based on cryptographic methods or may be from physical sources of noise, e.g. Zener diodes.